/**
 * 
 * 将一个数组的0全部移动到末尾  [1,0,3,0,4,0] ==> [1,3,4,0,0,0] 其顺序不变
 * 必须在原数组进行操作(题目要求)
 */

/**
 * 
 * @param arr 
 * @description 这个方法是O(n^2)的复杂度
 */


const zeroTOend = (arr:number[])=>{
    if(arr.length === 0) return
    let zerolength = 0
     /**此处的时间复杂度O(n) */
    for(let i = 0;i<arr.length - zerolength;i++){
        const item = arr[i]
        if(item === 0){
            zerolength++
            arr.push(0)
            /**此处的时间复杂度O(n) */
            arr.splice(i,1)
            i--
        }
    }
}


/**
 * @param arr 
 * @description 使用双指针  定义两个指针 i   j   j指向第一个0 i指向j后面的第一个非零  然后两个交换位置
 * @description  此函数的的时间复杂度为O(n)
 */

const zeroTOendByPointer = (arr:number[])=>{
    if(arr.length === 0) return
    let i;
    let j = -1
    for(i=0;i<arr.length;i++){
        const item = arr[i]
        if(item === 0){
            if(j < 0){
                j = i
            }
        }
        if(item > 0 && j > 0){
            const n = arr[j]
            arr[j] = arr[i]
            arr[i] = n

            j++
        }

    }
}






let arrzero =  [1,0,3,0,4,0]
//[]
// let arrzero =  [0,0,0,0,0,0,0,0,0,0,0]
zeroTOendByPointer(arrzero)
console.log(arrzero)